package org.practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zch
 */
public class CompositionZero {
    public static void main(String[] args) {
        int[] nums = new int[]{-1, 0, -1, 1, 2, -4, 0, 0};
        List<int[]> result = compositeZero(nums);
        int len = result.size();
        System.out.print("[");
        for (int i = 0; i < len - 1; i++) {
            System.out.print(Arrays.toString(result.get(i)) + ", ");
        }
        System.out.println(Arrays.toString(result.get(len - 1))+ "]");
    }

    private static List<int[]> compositeZero(int[] nums) {
        List<int[]> result = new ArrayList<>();
        int[] empty = new int[0];
        int len = nums.length;
        //数组长度小于3，不可能存在符合要求的三元组
        if (len < 3 ) {
            result.add(empty);
            return result;
        }
        Arrays.sort(nums);
        //排序后的数组最大的值小于等于0或最小的值大于等于0都不可能满足题目要求
        if (nums[0] >=0 || nums[len-1] <=0) {
            result.add(empty);
            return result;
        }
        return findTriples(nums, result);
    }

    private static List<int[]> findTriples0(int[] nums, List<int[]> result) {
        int sum;
        int len = nums.length;
        //穷举
        //存在的问题：1、会出现重复的结果; 2、时间复杂度高
        for (int i = 0; i < len - 2; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                for (int k = j + 1; k < len ; k++) {
                    sum = nums[i] + nums[j] + nums[k];
                    if (sum == 0) {
                        result.add(new int[]{nums[i], nums[j], nums[k]});
                    }
                }
            }
        }
        return result;
    }

    private static List<int[]> findTriples1(int[] nums, List<int[]> result) {
        int sum;
        int len = nums.length;
        for (int i = 0; i < len - 2; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                //已知数组有序，三元组和为零的情况有三种：[0, 0, 0]、[负数, 负数, 正数]、[负数, 正数, 正数]
                //所以第三层循环可以从后往前找
                for (int k = len - 1; k > j ; k--) {
                    sum = nums[i] + nums[j] + nums[k];
                    //去重: nums是排序后的数组，如果nums[i]与nums[i-1]相等，则nums[i]与nums[i-1]能得到相同的三元组
                    if (i > 0 && nums[i] == nums[i - 1]) {
                        continue;
                    }
                    if (sum == 0) {
                        result.add(new int[]{nums[i], nums[j], nums[k]});
                    }
                }
            }
        }
        return result;
    }

    private static List<int[]> findTriples(int[] nums, List<int[]> result) {
        int sum;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int left = i + 1;
            int right = len - 1;
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            while (left < right) {
                sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(new int[]{nums[left], nums[i], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (sum > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return result;
    }
}
